CS156 Fall 2014Practice Midterm

A Practice Midterm will appear here a week before the actual midterm.

To study for the midterm I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice midterm is below. Here are some facts about the actual midterm: (a) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (b) You should bring photo ID. (c) There will be more than one version of the test. Each version will be of comparable difficulty. (d) One problem (less typos) on the actual test will be from the practice test.

1. Briefly explain what the Turing Test is. Also define the term agent in the context of AI.
2. What is the PEAS description of a task environment? Give a fully spelt-out example of a episodic task environment.
3. Briefly describe iterative deepening depth first search and analyze its time complexity.
4. Give a concrete example where a problem solving agent using `A^\star`-search would not traverse a graph in the same way as one using breadth-first search. Give an example where depth first search outperforms `A^\star`-search.
5. Write a short python program which takes its command line arguments and sums them together. This program should make use of at least one function definition.
6. Given two admissable `A^\star` heuristic explain how to make a new heuristic which performs at least as well as either of them.
7. Briefly explain how genetic programming and local beam search are related hill-climbing algorithms.
8. What is the minimax function? Given an example of a situation in which a beta-cut might arise while running the mimimax algorithm with alpha-beta pruning.
9. Give pseudo-code for the AC3 algorithm.
10. Consider the following situation for four light switches on the control panel of a nuclear power plant: (a) The first and last can never both be on. (b) At least one light must be on. Express this as a propositional logic knowledge base.